/*
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]


*/
//迭代
class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        ListNode *prev = nullptr;
        ListNode *curr = head;
        while (curr)
        {
            ListNode *next = curr->next;
            curr->next = prev; //
            prev = curr;       //下一个要操作的结点
            curr = next;
        }
        return prev;
    }
};

//递归
class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        //
        if (!head || !head->next)
        {
            return head;
        }
        ListNode *newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};
